链表 |第 3 课（删除一个结点）

发表于

在单链表章节我们已经讨论了 链表的介绍 和 链表的插入。

我们阐述一下问题描述，帮助理解删除的过程。给定一个 ‘key’, 删除链表里第一个出现的结点。
要从链表里删除一个结点, 我们需要以下步骤。

  1. 找到待删结点的前驱结点。
  2. 修改前驱结点的Next.
  3. 释放被删除结点的内存。

建议: 在查看解决方案前，请自己尝试练习。

因为链表的每个结点都是通过 malloc() 动态分配的, 所以我们需要释放被删除结点的内存。

下面是C/C++代码

// 下面的代码已经通过编译

#include <stdio.h>
#include <stdlib.h>

// 结点定义
struct Node
{
    int data;
    struct Node *next;
};

/* 引用链表的头结点和一个整数值, 在链表前面插入一个新的结点 */
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data  = new_data;
    new_node->next = (*head_ref);
    (*head_ref)    = new_node;
}

/* 引用链表的头结点和一个 key, 然后删除首次遇见的结点 */
void deleteNode(struct Node **head_ref, int key)
{
    // 保存头结点
    struct Node* temp = *head_ref, *prev;

    // 如果要删除的结点恰巧是头结点
    if (temp != NULL && temp->data == key)
    {
        *head_ref = temp->next;   // 修改头结点
        free(temp);               // 释放头结点
        return;
    }

    // 查找要删除的 key, 因为我们要修改'prev->next'，所以需要跟踪前驱结点
    while (temp != NULL && temp->data != key)
    {
        prev = temp;
        temp = temp->next;
    }

    // 如果链表里没有这个 key
    if (temp == NULL) return;

    // 断开结点
    prev->next = temp->next;

    free(temp);  // 释放内存
}

// 下面的函数打印链表的内容
void printList(struct Node *node)
{
    while (node != NULL)
    {
        printf(" %d ", node->data);
        node = node->next;
    }
}

/* 测试函数*/
int main()
{
    /* 刚开始的空链表 */
    struct Node* head = NULL;

    push(&head, 7);
    push(&head, 1);
    push(&head, 3);
    push(&head, 2);

    puts("Created Linked List: ");
    printList(head);
    deleteNode(&head, 1);
    puts("\nLinked List after Deletion of 1: ");
    printList(head);
    return 0;
}


输出:

Created Linked List:
 2  3  1  7
Linked List after Deletion of 1:
 2  3  7